package com.shao.intelligentsnake;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 最短路策略，采用广度优先搜索算法。
 *
 * @author shaohuailin
 * @date 2024/4/21
 */
public class ShortActionStrategy implements ActionStrategy {

    // 起点位置
    private int startPosition;
    // 终点位置
    private int endPosition;
    // 探测器
    private Probe probe;

    public ShortActionStrategy(int startPosition, int endPosition, Probe probe) {
        this.startPosition = startPosition;
        this.endPosition = endPosition;
        this.probe = probe;
    }

    @Override
    public int[] apply() {
        int position = startPosition;
        // 初始化队列
        Queue<Integer> queue = new LinkedList<>();
        int not = 0, yes = 1;
        int[] visit = new int[0xFFFF];
        int[] path  = new int[0xFFFF];
        // 起点插入
        visit[position] = yes;
        queue.add(position);
        // 开始循环
        boolean findFood = false;
        while (!queue.isEmpty()) {
            if (findFood) {
                break;
            }
            // 取出当前节点
            int node = queue.poll();
            // 找下级节点，空则跳过
            int[] sub = this.probe.probe(node);
            if (sub.length == 0) {
                continue;
            }
            for (int s : sub) {
                if (visit[s] == not) {
                    visit[s] = yes;
                    path[s] = node;
                    queue.add(s);
                    if (s == endPosition) {
                        findFood = true;
                        break;
                    }
                }
            }
        }
        if (findFood) {
            int[] array = new int[0xFFFF];
            int id = array.length;
            int nextPosition = endPosition;
            while (nextPosition != position) {
                array[--id] = nextPosition;
                nextPosition = path[nextPosition];
            }
            int[] res = new int[array.length - id];
            System.arraycopy(array, id, res, 0, res.length);
            return res;
        }
        return new int[0];
    }
}
